{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Boats to Save People"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numRescueBoats"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #救生艇"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定数组<meta charset=\"UTF-8\" />&nbsp;<code>people</code>&nbsp;。<code>people[i]</code>表示第 <code>i</code><sup>&nbsp;</sup>个人的体重&nbsp;，<strong>船的数量不限</strong>，每艘船可以承载的最大重量为&nbsp;<code>limit</code>。</p>\n",
    "\n",
    "<p>每艘船最多可同时载两人，但条件是这些人的重量之和最多为&nbsp;<code>limit</code>。</p>\n",
    "\n",
    "<p>返回 <em>承载所有人所需的最小船数</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>people = [1,2], limit = 3\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>1 艘船载 (1, 2)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>people = [3,2,2,1], limit = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>3 艘船分别载 (1, 2), (2) 和 (3)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>people = [3,5,3,4], limit = 5\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>4 艘船分别载 (3), (3), (4), (5)</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= people.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= people[i] &lt;= limit &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [boats-to-save-people](https://leetcode.cn/problems/boats-to-save-people/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [boats-to-save-people](https://leetcode.cn/problems/boats-to-save-people/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2]\\n3', '[3,2,2,1]\\n3', '[3,5,3,4]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        res=0\n",
    "        i=0\n",
    "        j=len(people)-1\n",
    "        while i<=j: \n",
    "            if (people [i]+people [j])<=limit:\n",
    "                \n",
    "                i+=1\n",
    "                \n",
    "            j=j-1\n",
    "                \n",
    "            res+=1\n",
    "                \n",
    "                              \n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        if len(people)==0:\n",
    "            return 0\n",
    "        people.sort()\n",
    "        l=0\n",
    "        r=len(people)-1\n",
    "        res=0\n",
    "        while l<=r:\n",
    "            if people[l]+people[r]<=limit:\n",
    "                l=l+1\n",
    "            r=r-1\n",
    "            res=res+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        n = len(people)\n",
    "        i,j = 0,n-1\n",
    "        cnt = 0\n",
    "        while i <= j:\n",
    "            if people[i] + people[j] > limit:\n",
    "                j -= 1\n",
    "                cnt += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                cnt += 1\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        ans = 0\n",
    "        people.sort()\n",
    "        for i in people:\n",
    "            if i == limit :\n",
    "                people.remove(i)\n",
    "                ans += 1\n",
    "        left = 0\n",
    "        rigth = len(people) - 1\n",
    "        while left < rigth :\n",
    "            if people[left] + people[rigth] < limit :\n",
    "                ans += 1\n",
    "                left += 1\n",
    "                rigth -= 1\n",
    "            elif people[left] + people[rigth] == limit :\n",
    "                ans += 1\n",
    "                left += 1\n",
    "                rigth -= 1\n",
    "            elif people[left] + people[rigth] > limit :\n",
    "                ans += 1\n",
    "                rigth -= 1\n",
    "        if left == rigth :\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()  #[1, 2, 2, 3]\n",
    "        left,right,cnt = 0,len(people)-1,0\n",
    "        while left < right:\n",
    "            if people[left]+people[right]<= limit:\n",
    "                left +=1\n",
    "                right -= 1\n",
    "                cnt += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "                cnt += 1\n",
    "        if left == right:\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        res=0\n",
    "        i,j=0,len(people)-1\n",
    "        while i<=j:\n",
    "            if people[i]+people[j]<=limit:\n",
    "                i+=1\n",
    "                j-=1\n",
    "                res+=1\n",
    "            else:\n",
    "                j-=1\n",
    "                res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        if people is None or len(people)==0:\n",
    "            return 0\n",
    "        c = 0\n",
    "        people.sort()\n",
    "        l,r=0,len(people)-1\n",
    "        while l<=r:\n",
    "            if people[l]+people[r]<=limit:\n",
    "                l+=1\n",
    "            r-=1\n",
    "            c+=1\n",
    "        return c\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        # 滑动窗口\n",
    "        people = sorted(people)\n",
    "        left = 0\n",
    "        right = len(people) - 1\n",
    "        res = 0\n",
    "\n",
    "        while left <= right:\n",
    "            if people[right] + people[left] <= limit:\n",
    "               res += 1\n",
    "               right -= 1\n",
    "               left += 1\n",
    "               continue\n",
    "            res += 1\n",
    "            right -= 1\n",
    "        \n",
    "        return res\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        l, r = 0, len(people)-1\n",
    "        res = 0\n",
    "        people.sort()\n",
    "\n",
    "        while l <= r: # note here should be l <= r\n",
    "            if people[l] + people[r] <= limit:\n",
    "                l +=1\n",
    "                r -=1\n",
    "            else:\n",
    "                r -=1\n",
    "            res +=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        left,right,res = 0, len(people)-1 , 0\n",
    "\n",
    "        while left<=right:\n",
    "            if people[left] + people[right] > limit:\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=1\n",
    "                right-=1\n",
    "            res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        if not people:\n",
    "            return 0\n",
    "        people.sort()\n",
    "        i = 0\n",
    "        j = len(people) - 1\n",
    "        count = 0\n",
    "        while i <= j:\n",
    "            if people[i] + people[j] <= limit:\n",
    "                i += 1\n",
    "            j -= 1\n",
    "            count += 1\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        n=len(people)\n",
    "        people.sort()\n",
    "        left,right=0,n-1\n",
    "        ans=0\n",
    "        while left<=right:\n",
    "            if people[right]+people[left]<=limit:\n",
    "                left+=1\n",
    "            right-=1\n",
    "            ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        ans=0\n",
    "        i,j=0,len(people)-1\n",
    "        while i<=j:\n",
    "            if people[i]+people[j]>limit:\n",
    "                j-=1\n",
    "            else:\n",
    "                i+=1\n",
    "                j-=1\n",
    "            ans+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        weights = [0] * (limit + 1)\n",
    "        for weight in people:\n",
    "            weights[weight] += 1\n",
    "\n",
    "        i, j = 0, limit\n",
    "        res = 0\n",
    "        while i <= j:\n",
    "            while i <= j and weights[i] <= 0:\n",
    "                i += 1\n",
    "            while i <= j and weights[j] <= 0:\n",
    "                j -= 1\n",
    "            if i > j:\n",
    "                break\n",
    "            if i + j <= limit:\n",
    "                weights[i] -= 1\n",
    "            weights[j] -= 1\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        r=len(people)-1\n",
    "        l=0\n",
    "        ans=0\n",
    "        people.sort()\n",
    "        # print(people)\n",
    "        while r>=l:\n",
    "           k=limit-people[r]\n",
    "           c=1\n",
    "           while c<2 and l<r and people[l]<=k:\n",
    "               k-=people[l]\n",
    "               l+=1\n",
    "               c+=1\n",
    "        #    print(people[l],people[r],ans)\n",
    "           r-=1\n",
    "           ans+=1\n",
    "        return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        res = 0\n",
    "        people.sort(reverse=True)\n",
    "        l, r = 0, len(people) - 1\n",
    "        while l <= r:\n",
    "            if people[l] + people[r] <= limit:\n",
    "                res += 1\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            elif people[l] + people[r] > limit:\n",
    "                res += 1\n",
    "                l += 1\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        left = 0\n",
    "        right = len(people) - 1\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            while left < right and people[left] + people[right] > limit:\n",
    "                right -= 1\n",
    "                res += 1\n",
    "            \n",
    "            res += 1\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        \n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        count=0\n",
    "        people=sorted(people)\n",
    "        l=0;r=len(people)-1\n",
    "        while l<=r:\n",
    "            if people[l]+people[r]<=limit:\n",
    "                count+=1\n",
    "                l+=1;r-=1\n",
    "            else:\n",
    "                count+=1\n",
    "                r-=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people=sorted(people,reverse=True)#体重从大到小排列\n",
    "        counter=0\n",
    "        left,right=0,len(people)-1\n",
    "        while left<=right:\n",
    "            if people[left]+people[right]<= limit:###默认左右2端一个重的一个轻的在一个船\n",
    "                right-=1##如果满足，则右边轻的减一\n",
    "            left+=1#不管上述满不满足，重的均减一\n",
    "            counter+=1#不管上述满不满足，船都加一\n",
    "        return counter\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        i,j=0,len(people)-1\n",
    "        cnt=0\n",
    "        while(i<=j):\n",
    "            if people[i]+people[j]<=limit:\n",
    "                cnt+=1\n",
    "                i+=1\n",
    "                j-=1\n",
    "            else:\n",
    "                cnt+=1\n",
    "                j-=1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "\n",
    "        res = 0\n",
    "        l, r = 0, len(people) - 1\n",
    "        while l <= r:\n",
    "            remain = limit - people[r]\n",
    "            \n",
    "            if l < r and remain >= people[l]:\n",
    "                l += 1\n",
    "            r -= 1\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numRescueBoats(self, people, limit):\n",
    "        n = len(people)\n",
    "        people.sort()\n",
    "        left, right = 0, n - 1\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            if people[left] + people[right] <= limit:\n",
    "                left += 1\n",
    "            right -= 1\n",
    "            ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        # 双指针\n",
    "        people.sort(reverse=True)\n",
    "        l = 0\n",
    "        r = len(people) - 1\n",
    "        ans = 0\n",
    "        while r >= l:\n",
    "            if people[l] + people[r] <= limit:\n",
    "                r -= 1\n",
    "            l += 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people = sorted(people)\n",
    "        ans = 0\n",
    "        l, r = 0, len(people) - 1\n",
    "        while l <= r:\n",
    "            if people[l] + people[r] > limit:\n",
    "                r -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people, limit):\n",
    "        people.sort()  # 按重量排序\n",
    "        ans = 0  # 初始化结果变量\n",
    "        l = 0  # 初始化左指针\n",
    "        r = len(people) - 1  # 初始化右指针\n",
    "\n",
    "        while l <= r:\n",
    "            if l == r:\n",
    "                # 如果左右指针指向同一个人，只计算一个人的重量\n",
    "                s = people[l]\n",
    "            else:\n",
    "                s = people[l] + people[r]  # 计算当前船上的总重量\n",
    "\n",
    "            if s > limit:\n",
    "                r -= 1  # 如果总重量超过限制，减小右指针，舍弃最重的人\n",
    "            else:\n",
    "                l += 1  # 否则，增加左指针，舍弃最轻的人\n",
    "                r -= 1  # 同时减小右指针，舍弃最重的人\n",
    "            ans += 1  # 每次循环结束，表示一艘船\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        ans = 0\n",
    "        people.sort()\n",
    "        for i in people:\n",
    "            if i == limit :\n",
    "                people.remove(i)\n",
    "                ans += 1\n",
    "        left = 0\n",
    "        rigth = len(people) - 1\n",
    "        while left < rigth :\n",
    "            if people[left] + people[rigth] < limit :\n",
    "                ans += 1\n",
    "                left += 1\n",
    "                rigth -= 1\n",
    "            elif people[left] + people[rigth] == limit :\n",
    "                ans += 1\n",
    "                left += 1\n",
    "                rigth -= 1\n",
    "            elif people[left] + people[rigth] > limit :\n",
    "                ans += 1\n",
    "                rigth -= 1\n",
    "        if left == rigth :\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        l, r = 0, len(people) -1\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            if people[l] + people[r] > limit:\n",
    "                r -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        i, j = 0, len(people) - 1\n",
    "        ans = 0\n",
    "        while i <= j:\n",
    "            if people[i] + people[j] <= limit:\n",
    "                i += 1\n",
    "            j -= 1\n",
    "            ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 贪心 + 排序 + 双指针\n",
    "# 优先让剩余的人中最轻的人和最重的人配对：\n",
    "# 1. 如果超重，则最重的人无法和别人配对乘船，只能单独离开，考虑次重的人\n",
    "# 2. 如果不超重，则可以完成配对，两个人乘船离开，然后考虑次轻和次重的人\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        # 对people从小到大进行排序，方便使用双指针     \n",
    "        people.sort()\n",
    "        # 初始化left和right两个指针，指向一头一尾；初始化答案变量ans \n",
    "        left, right, ans = 0, len(people)-1, 0\n",
    "        # 进行循环，退出循环条件为两指针相遇，表示所有的人都得救\n",
    "        while left <= right:\n",
    "            # 如果两个人相加重量超过limit，则只让重的人，即people[right]，单独乘船离开，right递减1\n",
    "            if people[left] + people[right] > limit:\n",
    "                right -= 1\n",
    "            # 如果两个人相加重量不超过limit，则让这一轻一重，两个人一起乘船离开，right递减1，left递增1\n",
    "            else:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            # 每轮匹配，都会用上一艘救生艇，更新ans变量\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        hash_ = [0] * 30001\n",
    "        max_ = 0\n",
    "        for num in people:\n",
    "            hash_[num] += 1\n",
    "            max_ = max(num, max_)\n",
    "        #print(Counter(hash_))\n",
    "        #people = limit - max_ \n",
    "        def board(people, hash_):\n",
    "            for i in range(people, 0, -1):\n",
    "                if hash_[i] >= 1:\n",
    "                    hash_[i] -= 1\n",
    "                    break\n",
    "        cnt = 0\n",
    "        for peop in range(max_, 0, -1):\n",
    "            while hash_[peop] >= 1:\n",
    "                #print(peop)\n",
    "                hash_[peop] -= 1\n",
    "                cnt += 1\n",
    "                board(limit - peop, hash_)\n",
    "        return cnt\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        n = len(people)\n",
    "        left, right = 0, n - 1\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            if people[left] + people[right] > limit:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 贪心 + 排序 + 双指针\n",
    "# 优先让剩余的人中最轻的人和最重的人配对：\n",
    "# 1. 如果超重，则最重的人无法和别人配对乘船，只能单独离开，考虑次重的人\n",
    "# 2. 如果不超重，则可以完成配对，两个人乘船离开，然后考虑次轻和次重的人\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        # 对people从小到大进行排序，方便使用双指针     \n",
    "        people.sort()\n",
    "        # 初始化left和right两个指针，指向一头一尾；初始化答案变量ans \n",
    "        left, right, ans = 0, len(people)-1, 0\n",
    "        # 进行循环，退出循环条件为两指针相遇，表示所有的人都得救\n",
    "        while left <= right:\n",
    "            # 如果两个人相加重量超过limit，则只让重的人，即people[right]，单独乘船离开，right递减1\n",
    "            if people[left] + people[right] > limit:\n",
    "                right -= 1\n",
    "            # 如果两个人相加重量不超过limit，则让这一轻一重，两个人一起乘船离开，right递减1，left递增1\n",
    "            else:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            # 每轮匹配，都会用上一艘救生艇，更新ans变量\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        n = len(people)\n",
    "        people.sort()\n",
    "        ans = 0\n",
    "        i, j = 0, n-1\n",
    "        while i < j:\n",
    "            if people[i] + people[j] > limit:\n",
    "                ans += 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                ans += 1\n",
    "                i += 1\n",
    "                j -= 1\n",
    "        if i == j:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        l=0\n",
    "        r=len(people)-1\n",
    "        result=0\n",
    "        people.sort()\n",
    "        while l<=r:\n",
    "            if people[l]+people[r]<=limit:\n",
    "                l+=1\n",
    "            r-=1\n",
    "            result+=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people = sorted(people, key=lambda x: x)\n",
    "        count = 0\n",
    "\n",
    "\n",
    "        i, j = 0, len(people) - 1\n",
    "        while i <= j:\n",
    "            if i == j:\n",
    "                count += 1\n",
    "                i += 1\n",
    "            elif people[i] + people[j] <= limit:\n",
    "                count += 1\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                count += 1\n",
    "                j -= 1\n",
    "                \n",
    "        return(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        n = len(people)\n",
    "        people.sort()\n",
    "        begin = 0\n",
    "        end = n-1\n",
    "        count = 0\n",
    "        while end >= begin:\n",
    "            if people[begin] + people[end] <= limit:\n",
    "                begin += 1\n",
    "            count += 1\n",
    "            end -= 1\n",
    "        return count\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        # 对撞指针\n",
    "        res = 0\n",
    "        # people.sort() # 默认的是从小到大啊啊啊啊啊啊啊啊啊啊\n",
    "        people.sort(reverse=True) # 从大到小。。\n",
    "        i = 0 # 头\n",
    "        j = len(people) - 1 # 尾\n",
    "        \n",
    "        # 更简单的实现方式，使用于sort()\n",
    "        # while i <= j:\n",
    "        #     if people[i] + people[j] <= limit:\n",
    "        #         i += 1\n",
    "        #     j -= 1\n",
    "        #     res += 1\n",
    "        \n",
    "        while i <= j:\n",
    "            if people[i] + people[j] <= limit:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "                # j -= 1\n",
    "            res += 1 # 放在这里，每操作一次都能+1\n",
    "\n",
    "            # if i < j and people[i] + people[j] <= limit:\n",
    "            #     res += 1\n",
    "            #     i += 1\n",
    "            #     j -= 1\n",
    "            # elif i == j:\n",
    "            #     res += 1     \n",
    "            # else:\n",
    "            #     res += 1\n",
    "            #     i += 1\n",
    "            # 以上，每个条件下其实都要res+1，可以直接移出\n",
    "\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        ans = 0\n",
    "        people.sort()\n",
    "        for i in people:\n",
    "            if i == limit :\n",
    "                people.remove(i)\n",
    "                ans += 1\n",
    "        left = 0\n",
    "        rigth = len(people) - 1\n",
    "        while left < rigth :\n",
    "            if people[left] + people[rigth] < limit :\n",
    "                ans += 1\n",
    "                left += 1\n",
    "                rigth -= 1\n",
    "            elif people[left] + people[rigth] == limit :\n",
    "                ans += 1\n",
    "                left += 1\n",
    "                rigth -= 1\n",
    "            elif people[left] + people[rigth] > limit :\n",
    "                ans += 1\n",
    "                rigth -= 1\n",
    "        if left == rigth :\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        l = 0\n",
    "        r = len(people)-1\n",
    "        res = 0\n",
    "        people.sort()\n",
    "        while(l<=r):\n",
    "            if people[r] + people[l] <= limit:\n",
    "                res = res + 1\n",
    "                l = l + 1\n",
    "                r = r - 1\n",
    "            else:\n",
    "                res = res + 1\n",
    "                r = r - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        left = 0\n",
    "        right = len(people)-1\n",
    "        count = 0\n",
    "        while left <= right:\n",
    "            if people[left]+people[right] <= limit:\n",
    "                left += 1\n",
    "            count += 1\n",
    "            right -= 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        if len(people) == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            people.sort()\n",
    "            i = 0\n",
    "            j = len(people) - 1\n",
    "            boat = 0\n",
    "            while i <= j:\n",
    "                if people[i] + people[j] <= limit:\n",
    "                    boat += 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    boat += 1\n",
    "                j -= 1\n",
    "            return boat\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        if people is None or len(people)==0:\n",
    "            return 0\n",
    "        c = 0\n",
    "        people.sort()\n",
    "        l,r=0,len(people)-1\n",
    "        while l<=r:\n",
    "            if people[l]+people[r]<=limit:\n",
    "                l+=1\n",
    "            r-=1\n",
    "            c+=1\n",
    "        return c\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        n_people = len(people)\n",
    "        people.sort()\n",
    "\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        right = n_people - 1\n",
    "        while left < right:\n",
    "            if people[left] + people[right] > limit:\n",
    "                right -= 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "                left += 1\n",
    "                ans += 1\n",
    "        return ans + 1 if left == right else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        Q = deque(sorted(people))\n",
    "        ans =0\n",
    "        while Q:\n",
    "            tail = Q.pop() \n",
    "            if Q and Q[0] + tail <= limit:\n",
    "                Q.popleft()\n",
    "            ans += 1\n",
    "        return ans \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 贪心 + 排序 + 双指针\n",
    "# 优先让剩余的人中最轻的人和最重的人配对：\n",
    "# 1. 如果超重，则最重的人无法和别人配对乘船，只能单独离开，考虑次重的人\n",
    "# 2. 如果不超重，则可以完成配对，两个人乘船离开，然后考虑次轻和次重的人\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        # 对people从小到大进行排序，方便使用双指针     \n",
    "        people.sort()\n",
    "        # 初始化left和right两个指针，指向一头一尾；初始化答案变量ans \n",
    "        left, right, ans = 0, len(people)-1, 0\n",
    "        # 进行循环，退出循环条件为两指针相遇，表示所有的人都得救\n",
    "        while left <= right:\n",
    "            # 如果两个人相加重量超过limit，则只让重的人，即people[right]，单独乘船离开，right递减1\n",
    "            if people[left] + people[right] > limit:\n",
    "                right -= 1\n",
    "            # 如果两个人相加重量不超过limit，则让这一轻一重，两个人一起乘船离开，right递减1，left递增1\n",
    "            else:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            # 每轮匹配，都会用上一艘救生艇，更新ans变量\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        # 先排序\n",
    "        people.sort()\n",
    "        # 获取数组长度\n",
    "        n = len(people)\n",
    "        # 寻找两人组\n",
    "        # 最左边的位置\n",
    "        left = 0\n",
    "        # 最右边的位置\n",
    "        right = n - 1\n",
    "        # 船的数量\n",
    "        ans = 0\n",
    "        while left <= right :\n",
    "            # 1、如果 people[left] + people[right] <= limit\n",
    "            # 说明 people[left] 和 people[right] 可以同船\n",
    "            if people[left] + people[right] <= limit :\n",
    "                #  此时船的数量加一\n",
    "                ans += 1\n",
    "                # 两个指针分别往中间靠拢\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            # 如果 people[left] + people[right] > limit\n",
    "            # 说明 people[left] 和 people[right] 不可以同船\n",
    "            else:\n",
    "                # 由于题目说明了人的重量不会超过 limit\n",
    "                # people[right] 需要独自坐船，船的数量加一\n",
    "                ans += 1\n",
    "                # people[right] 坐船后\n",
    "                # right 需要向内移动，寻找新的组合\n",
    "                right -= 1\n",
    "        # 返回结果\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()  # 将人员按体重从小到大排序\n",
    "        left, right = 0, len(people) - 1\n",
    "        boats = 0\n",
    "\n",
    "        while left <= right:\n",
    "            if left == right:\n",
    "                boats += 1\n",
    "                break\n",
    "\n",
    "            if people[left] + people[right] <= limit:\n",
    "                left += 1\n",
    "            right -= 1\n",
    "            boats += 1\n",
    "\n",
    "        return boats\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        ans = 0\n",
    "        people.sort()\n",
    "        for i in people:\n",
    "            if i == limit :\n",
    "                people.remove(i)\n",
    "                ans += 1\n",
    "        left = 0\n",
    "        rigth = len(people) - 1\n",
    "        while left < rigth :\n",
    "            if people[left] + people[rigth] < limit :\n",
    "                ans += 1\n",
    "                left += 1\n",
    "                rigth -= 1\n",
    "            elif people[left] + people[rigth] == limit :\n",
    "                ans += 1\n",
    "                left += 1\n",
    "                rigth -= 1\n",
    "            elif people[left] + people[rigth] > limit :\n",
    "                ans += 1\n",
    "                rigth -= 1\n",
    "        if left == rigth :\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        boats = 0\n",
    "        people.sort()\n",
    "        l, r = 0, len(people)-1\n",
    "\n",
    "\n",
    "        while l <=r:\n",
    "            if l<r and people[l]+people[r]>limit:\n",
    "                r-=1\n",
    "                boats+=1\n",
    "            elif l<r and people[l]+people[r]<=limit:\n",
    "                l+=1\n",
    "                r-=1\n",
    "                boats+=1\n",
    "            elif l == r:\n",
    "                boats+=1\n",
    "                break\n",
    "\n",
    "    \n",
    "            \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "        return boats\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "\n",
    "        n=len(people)\n",
    "        people.sort()\n",
    "        l=0\n",
    "        r=n-1\n",
    "        cnt=0\n",
    "        while l<r:\n",
    "            if people[l]+people[r]>limit:\n",
    "                r=r-1\n",
    "                cnt+=1\n",
    "            elif people[l]+people[r]<=limit:\n",
    "                cnt+=1\n",
    "                r=r-1\n",
    "                l=l+1\n",
    "        if l==r:\n",
    "            cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        l = 0\n",
    "        r = len(people)-1\n",
    "        res = 0\n",
    "        while l<=r:\n",
    "            if people[l]+people[r]<=limit:\n",
    "                l+=1\n",
    "            r-=1\n",
    "            res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        # 每个船只能坐两个人，对撞指针\n",
    "        cnt = 0\n",
    "        people.sort()\n",
    "        size = len(people)\n",
    "        left, right = 0, size - 1\n",
    "        while left <= right:\n",
    "            if left == right:\n",
    "                cnt += 1\n",
    "                break\n",
    "            s = people[left] + people[right]\n",
    "            if s <= limit:\n",
    "                cnt += 1\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "                right -= 1\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        if len(people) == 0 or people is None or limit == 0:\n",
    "            return 0\n",
    "        \n",
    "        people.sort()   #按体重升序排列\n",
    "        \n",
    "        cnt = 0\n",
    "        left = 0\n",
    "        right = len(people)-1\n",
    "        \n",
    "        while left <= right:\n",
    "            if people[left] + people[right] <= limit:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "                cnt += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "                cnt += 1\n",
    "                \n",
    "        return cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        n = len(people)\n",
    "        left,right = 0,n-1\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            if people[left]+people[right]<=limit:\n",
    "                ans += 1\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                right -= 1\n",
    "                ans += 1\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        people.sort()\n",
    "        left,right = 0,len(people)-1\n",
    "        ans = 0\n",
    "        mid = ceil(limit)\n",
    "        while left<=right:\n",
    "            if people[left]>mid:\n",
    "                ans += right-left+1\n",
    "                break\n",
    "            if people[left]+people[right]>limit:\n",
    "                ans += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                ans += 1\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people = sorted(people, key=lambda x: x)\n",
    "        count = 0\n",
    "\n",
    "\n",
    "        i, j = 0, len(people) - 1\n",
    "        while i <= j:\n",
    "            if people[i] + people[j] <= limit:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                j -= 1\n",
    "            count += 1\n",
    "                \n",
    "        return(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        boats = 0\n",
    "        people.sort()\n",
    "        l, r = 0, len(people)-1\n",
    "\n",
    "\n",
    "        while l <=r:\n",
    "            if  people[l]+people[r]>limit:\n",
    "                r-=1\n",
    "                boats+=1\n",
    "            elif people[l]+people[r]<=limit:\n",
    "                l+=1\n",
    "                r-=1\n",
    "                boats+=1\n",
    "     \n",
    "        return boats\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        # 贪心策略：排序，一次带一个最轻的和最重的，如果大于limit,只带最终的，否则全带\n",
    "        people.sort() \n",
    "        count = 0\n",
    "        left =0 \n",
    "        right=len(people)-1\n",
    "        while left<=right:\n",
    "            if people[left]+people[right] >limit:\n",
    "                count+=1\n",
    "                right-=1\n",
    "            else:\n",
    "                count+=1\n",
    "                right-=1\n",
    "                left+=1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        left =0 \n",
    "        right = len(people) -1\n",
    "        ans =0\n",
    "        while left <= right :\n",
    "            if people[left] + people[right]<limit:\n",
    "                ans += 1\n",
    "                left +=1\n",
    "                right -=1\n",
    "            elif people[left] + people[right] ==limit:\n",
    "                ans +=1\n",
    "                right -=1\n",
    "                left +=1\n",
    "            elif people[left] + people[right] >limit:\n",
    "                ans +=1\n",
    "                right -=1\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        ans=0\n",
    "        people.sort()\n",
    "        i,j=0,len(people)-1\n",
    "        while i<=j:\n",
    "            if people[j]+people[i]<=limit:\n",
    "                ans+=1\n",
    "                j-=1\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "                ans+=1\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        if limit == 0 or not people:\n",
    "            return 0\n",
    "        people.sort()\n",
    "        if people[-1] > limit:\n",
    "            return -1\n",
    "        len_people = len(people)\n",
    "        l = 0\n",
    "        r = len_people - 1\n",
    "        res = 0\n",
    "        while l <= r:\n",
    "            if l == r:\n",
    "                res += 1\n",
    "                r -= 1\n",
    "            else:\n",
    "                lv = people[l]\n",
    "                rv = people[r]\n",
    "                if lv + rv <= limit:\n",
    "                    res += 1\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    res += 1\n",
    "                    r -= 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "\n",
    "        people.sort()\n",
    "\n",
    "        L, R = 0, len(people)-1\n",
    "        cnt = 0\n",
    "        while L < R:\n",
    "            while L < R and people[L] + people[R] > limit:\n",
    "                R -= 1\n",
    "                cnt += 1\n",
    "            while L < R and people[L] + people[R] <= limit:\n",
    "                R -= 1\n",
    "                L += 1\n",
    "                cnt += 1\n",
    "            if L == R:\n",
    "                cnt += 1\n",
    "        return cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people = sorted(people, key=lambda x: x)\n",
    "        count = 0\n",
    "\n",
    "\n",
    "        i, j = 0, len(people) - 1\n",
    "        while i <= j:\n",
    "            if people[i] + people[j] <= limit:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                j -= 1\n",
    "            count += 1\n",
    "                \n",
    "        return(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        count = 0\n",
    "        people.sort()\n",
    "        people = people[::-1]\n",
    "        p = len(people) - 1\n",
    "        for i in range (len(people)):\n",
    "            if i + 1 == p:\n",
    "                if people[i] + people[p] <= limit:\n",
    "                    count += 1\n",
    "                    break\n",
    "                else:\n",
    "                    count += 2\n",
    "                    break\n",
    "            elif i == p:\n",
    "                count += 1\n",
    "                break\n",
    "            if people[i] + people[p] <= limit:\n",
    "                count += 1\n",
    "                p -= 1\n",
    "            else:\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        n = len(people)\n",
    "        people.sort()\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        cnt = 0\n",
    "        while left <= right:\n",
    "            if people[left] + people[right] > limit:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            cnt += 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\r\n",
    "        people.sort()\r\n",
    "        n=len(people)\r\n",
    "        l,r=0,n-1\r\n",
    "        ret=0\r\n",
    "        while l<=r:\r\n",
    "            s=people[l]+people[r]\r\n",
    "            if s>limit:\r\n",
    "                r-=1\r\n",
    "            else:\r\n",
    "                l+=1\r\n",
    "                r-=1\r\n",
    "            ret+=1\r\n",
    "\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        n=len(people)\n",
    "        ans=0\n",
    "        l,r=0,n-1\n",
    "        while l <= r:\n",
    "            if people[r] + people[l] <= limit:\n",
    "                l+=1\n",
    "            r-=1\n",
    "            ans+=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people = sorted(people, key=lambda x: x)\n",
    "        count = 0\n",
    "\n",
    "\n",
    "        i, j = 0, len(people) - 1\n",
    "        while i <= j:\n",
    "            if i == j:\n",
    "                count += 1\n",
    "                i += 1\n",
    "            elif people[i] + people[j] <= limit:\n",
    "                count += 1\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                count += 1\n",
    "                j -= 1\n",
    "                \n",
    "        return(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        l = 0\n",
    "        r = len(people)-1\n",
    "        ans = 0\n",
    "        while l<=r:\n",
    "            if l==r:\n",
    "                ans += 1\n",
    "                return ans\n",
    "            elif people[l]+people[r] <= limit:\n",
    "                l+=1\n",
    "                r-=1\n",
    "                ans+=1\n",
    "            else:\n",
    "                r-=1\n",
    "                ans+=1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        res, left, right = 0, 0, len(people) - 1\n",
    "        while left <= right:\n",
    "            total = 0\n",
    "            if left <= right and total + people[right] <= limit:\n",
    "                total += people[right]\n",
    "                right -= 1\n",
    "            if left <= right and total + people[left] <= limit:\n",
    "                total += people[left]\n",
    "                left += 1\n",
    "            res += 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        n = len(people)\n",
    "        people.sort()\n",
    "\n",
    "        l = 0\n",
    "        r = n-1\n",
    "        res = 0\n",
    "\n",
    "        while l < r:\n",
    "            if people[l]+people[r] <= limit:\n",
    "                l+=1\n",
    "                r-=1\n",
    "            else:\n",
    "                r-=1\n",
    "            \n",
    "            res+=1\n",
    "        \n",
    "        if l==r:\n",
    "            res+=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        if people is None or len(people) == 0:\n",
    "            return 0\n",
    "        l, r = 0, len(people) - 1\n",
    "        people.sort()\n",
    "        n = 0\n",
    "        while l <= r:\n",
    "            if people[l] + people[r] <= limit:\n",
    "                l += 1\n",
    "            r -= 1\n",
    "            n += 1\n",
    "        return n\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        i,j=0,len(people)-1\n",
    "        res=0\n",
    "        while i<=j:\n",
    "            if people[i]+people[j]<=limit:\n",
    "                i+=1\n",
    "            j-=1\n",
    "            res+=1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 贪心 + 排序 + 双指针\n",
    "# 优先让剩余的人中最轻的人和最重的人配对：\n",
    "# 1. 如果超重，则最重的人无法和别人配对乘船，只能单独离开，考虑次重的人\n",
    "# 2. 如果不超重，则可以完成配对，两个人乘船离开，然后考虑次轻和次重的人\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        # 对people从小到大进行排序，方便使用双指针     \n",
    "        people.sort()\n",
    "        # 初始化left和right两个指针，指向一头一尾；初始化答案变量ans \n",
    "        left, right, ans = 0, len(people)-1, 0\n",
    "        # 进行循环，退出循环条件为两指针相遇，表示所有的人都得救\n",
    "        while left <= right:\n",
    "            # 如果两个人相加重量超过limit，则只让重的人，即people[right]，单独乘船离开，right递减1\n",
    "            if people[left] + people[right] > limit:\n",
    "                right -= 1\n",
    "            # 如果两个人相加重量不超过limit，则让这一轻一重，两个人一起乘船离开，right递减1，left递增1\n",
    "            else:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            # 每轮匹配，都会用上一艘救生艇，更新ans变量\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        ans = 0\n",
    "        light, heavy = 0, len(people) -1\n",
    "        while light <= heavy:\n",
    "            s = people[light] + people[heavy]\n",
    "            if s > limit:\n",
    "                heavy -= 1\n",
    "            else:\n",
    "                light += 1\n",
    "                heavy -= 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        size = len(people)\n",
    "        left, right = 0, size - 1\n",
    "        ans = 0\n",
    "        while left < right:\n",
    "            if people[left] + people[right] > limit:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            ans += 1\n",
    "        if left == right:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        start, end, i = 0, len(people)-1, 0\n",
    "        for i in range(10000000):\n",
    "            if start<=end:\n",
    "                if people[start]+people[end] > limit:\n",
    "                    end -= 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    start += 1\n",
    "                    end -= 1\n",
    "                    i += 1\n",
    "            else:\n",
    "                break\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        if not people:\n",
    "            return 0\n",
    "        people.sort()\n",
    "        start, end = 0, len(people) - 1\n",
    "        result = 0\n",
    "        while start <= end:\n",
    "            if people[start] + people[end] <= limit:\n",
    "                result += 1\n",
    "                end -= 1\n",
    "                start += 1\n",
    "            else:\n",
    "                result += 1\n",
    "                end -= 1\n",
    "        return result\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        people.sort()\n",
    "        ans=0    \n",
    "        j=len(people)-1 \n",
    "        i=0 \n",
    "        while i<=j:\n",
    "            if(j-i>0 and people[i]+people[j]<=limit):\n",
    "                i+=1\n",
    "            j-=1\n",
    "            ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        n = len(people)\n",
    "        people.sort()\n",
    "        res = 0\n",
    "        i, j = 0, n - 1\n",
    "        while i <= j:\n",
    "            if people[i] + people[j] > limit:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRescueBoats(self, people: List[int], limit: int) -> int:\n",
    "        if people==None or len(people)==0:\n",
    "            return 0\n",
    "        people=sorted(people)\n",
    "        i=0\n",
    "        j=length_hint(people)-1\n",
    "        res=0\n",
    "        while(i<=j):\n",
    "            if people[i]+people[j] <= limit:\n",
    "                i =i+1\n",
    "            j =j-1\n",
    "            res=res+1\n",
    "           \n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
